
//1782.统计点对的数目
class Solution {
public:
    vector<int> countPairs(int n, vector<vector<int>>& edges, vector<int>& queries) {
        vector<int> count(n+1);  //存储每一个数字与多少条边相连
        map<pair<int,int>,int>  repeat;  //记录i<j中每个组合出现的次数

        for(auto e:edges)
        {
            int x=e[0],y=e[1];
            if(x>y) swap(x,y);   //保证x始终是小于y的，方便map进行计数
            count[x]++,count[y]++;
            repeat[{x,y}]++;
        }

        //此时count存储了从1----n中每个数其他数相连的边数
        //此题就转化为了在数组count中找两个不同的位置使其之和>queries[i]即可
        //但是直接使用count中的数据必定会出现重复数据,比如[1,2]的范围直接将count[1]+count[2]就会多计数
        //对于重复数据需要进行处理

        //可以使用同向双指针进行实现
        vector<int> tmp(count);
        sort(tmp.begin(),tmp.end());         //将count进行排序
        vector<int> ret(queries.size());
        for(int i=0;i<queries.size();i++)
        {
            int left=1,right=n,num=0;
            while(left<right)
            {
                if(tmp[left]+tmp[right]<=queries[i]) left++;
                else 
                {
                    ret[i]+=right-left;
                    right--;
                }
            }
            //对重复数据进行处理
            for(auto [pa,num]:repeat)
            {
                int x=pa.first,y=pa.second;
                if(count[x]+count[y]>queries[i]&&count[x]+count[y]-num<=queries[i])
                ret[i]--;
            }
        }
        return ret;
    }
};